package com.shm.leetcode;

/**
 * 188. 买卖股票的最佳时机 IV
 * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
 *
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
 *
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：k = 2, prices = [2,4,1]
 * 输出：2
 * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
 * 示例 2：
 *
 * 输入：k = 2, prices = [3,2,6,5,0,3]
 * 输出：7
 * 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
 *      随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
 *
 * @author SHM
 */
public class MaxProfitVI {

    public int maxProfit(int k, int[] prices) {
        if (prices==null||prices.length==0){
            return 0;
        }
        return dfs(prices,k,0,0,0);
    }

    /**
     * 超时
     * 递归
     * 我们先回归一下交易两次的状态转换图
     *
     *
     * 交易两次的状态是由初始开始，转入买入1状态(买了一股)，再到卖出1(卖出一股)，之后是买入2 也就是第二次买入，卖出2 即第二次卖出。
     * 而交易k次可以理解为交易两次的延伸，即在第二次卖出后，我们可以继续第三次买入，第三次卖出。。。 直到第k次买入，第k次卖出。
     *
     *
     * 一开始处于初始状态，也就是什么都不做，不买也不卖
     * 初始状态只能转向买入1状态(第一次买入股票)，也就是买入一股；当买入一股后，我们有两种选择:
     *
     * 可以立马转向卖出1状态(第一次卖出股票)
     * 或者转入保持不动状态，相当于手里一直有这一股，等待一个好时机之后再卖出。
     * 在卖出1状态时:
     *
     * 我们可以立马转入买入2状态(第二次买入股票)
     * 或者转入保持不动状态，相当于此时手里没有股票了，等待一个好时机后再买入。
     * 后面的买入2、卖出2、一直到买入k、卖出k都是一样的
     * 卖出k 执行完后，就只能转入到交易结束状态了，后面就无法再买卖了。
     *
     * 我们可以用三个变量来表示买卖k次的交易状态
     *
     * index，用来表示当前是哪一天
     * status，用来表示当前是买入、还是卖出
     * count，用来表示交易了几次
     * 如果状态是是买入:
     *
     * 那么可以保持不动
     * 或者马上卖掉
     * 如果状态是卖出:
     *
     * 可以保持不动(等待更好的股价出现，暂时不买)
     * 或者立马再买一股
     * 同时将count数+1，表示交易过一次了
     * 对于数组[1,2,3,4,5,6,7,8,9]其递归调用树如下:
     *
     *
     * 第一次只能买入，对应上图也就是节点1的买1，当然也可以选择不买，也就是不动。
     * 第一次买之后可以立刻卖掉，也就是上图中根--买1--> 1 --卖1--> 2这条路线。这就对应了第二张图中买入1转换到卖出1的过程。
     * 而第一次买入之后，对应到上图就是根 --买1--> 1 --不动--> 2这条路线。对应第二张图中买1后转入到保持不动这个过程。
     *
     * 卖1到买2,买2到卖2，买3到卖3，买k到卖k这之间的转换关系也是类似的，大家可以看下图二和图三，对比一下这个关系。
     * 第k次卖出后就无法再交易了，所以从调用树上来看，后面就不会再有调用的子节点了。
     *
     * 作者：wang_ni_ma
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/si-chong-jie-fa-tu-jie-188mai-mai-gu-piao-de-zui-j/
     * @param prices
     * @param k
     * @param count
     * @param status
     * @param index
     * @return
     */
    public int dfs(int[] prices,int k,int count,int status,int index){
        if (index==prices.length||count==k){
            return 0;
        }
        int a=0,b=0,c=0;
        //不动
//        a=dfs(prices,k,count,0,index+1); //易错点
        a=dfs(prices,k,count,status,index+1);
        if (status==1){
            //卖出
            b=dfs(prices,k,count+1,0,index+1)+prices[index];
        }else {
            //买入
            c=dfs(prices,k,count,1,index+1)-prices[index];
        }
        return Math.max(Math.max(a,b),c);
    }

    /**
     * 动态规划
     * 在递归实现时，我们用了三个变量：index、status、k。这里我们定义一个三维数组
     * dp[n][k][2] 这里的n表示天数
     *
     * dp[i][j][0]：表示第i天交易了j次时卖出后的累计最大利润
     * dp[i][j][1]：表示第i天交易了j次时买入后的累计最大利润
     * 注意，当 j==k 时，dp[i][j][1]已经没有意义了，因为交易了k次之后，就不能再买入了。
     *
     *
     *
     * dp[i][0][0]：对应于初始状态，第i天0次交易卖出，既然都没交易，那何来卖出呢，所以只能是0。
     * dp[i][0][1]和dp[i][1][0] 这两个是一对，对应到上图中就是第一次买入、第一次卖出。
     * dp[i][1][1]和dp[i][2][0] 这两个也是一对，对应到上图中就是第二次买入、第二次卖出。
     * dp[i][k-1][1]和dp[i][k][0] 这两个是一堆，对应到上图是第k次买入、第k次卖出。
     * 由于我们把dp[0][0][0]作为一个初始状态，真正的买和卖是从dp[0][0][1]、dp[0][1][0]开始的，所以这里的一买、一卖，在第二维度中正好有一个+1的变化：
     *
     *
     * dp[0][0][1]
     * dp[0][1][0]
     * 所以推广到第k次的时候，就变成了：
     *
     *
     * dp[i][k-1][1]
     * dp[i][k][0]   k这个维度会有一个+1的变化
     * 也是在第二维度有一个+1的变化。
     * 因为到了dp[i][k][0]整个交易就结束了，所以dp[i][k][1]实际上是不存在的。
     *
     * 再看一下状态转换公式如何推导的
     *
     *
     * 买入1这个状态只能从两个地方转换来，买入1本身(保持不动)，或者是初始状态转换而来。
     * 而卖出1这个状态，也只能从两个地方转换而来，卖出1本身(保持不动)，或者从买入1转来。
     * 同样，第二次买入只能从 第一次买入转换来，或者保持不动。
     * 第二次卖出只能从第二次买入转换来，或者保持不动。
     *
     * 那么第一次买入、卖出，第二次买入、卖出的推导公式如下：
     *
     *
     * 第一次买入：从初始状态转换而来，或者第一次买入后保持不动
     * dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])
     *
     * 第一次卖出：从第一次买入转换而来，或者第一次卖出后保持不动
     * dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][0][1]+prices[i])
     *
     * 第二次买入：从第一次卖出转换而来，或者第二次买入后保持不动
     * dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][1][0]-prices[i])
     *
     * 第二次卖出：从第二次买入转换而来，或者第二次卖出后保持不动
     * dp[i][2][0] = max(dp[i-1][2][0],dp[i-1][1][1]+prices[i])
     *
     * 第三次买入：
     * dp[i][2][1] = max(dp[i-1][2][1],dp[i-1][2][0]-prices[i])
     *
     * 第三次卖出：
     * dp[i][3][0] = max(dp[i-1][3][0],dp[i-1][2][1]+prices[i])
     * 进而我们将公式泛化推广到k次交易：
     *
     *
     * 第k次买入： 从第k-1次卖出转换而来，或者第k次买入后保持不动
     * dp[i][j-1][1] = max(dp[i-1][j-1][1],dp[i-1][j-1][0]-prices[i])
     *
     * 第k次卖出： 从第k次买入后转换而来，或者是第k次卖出后保持不动
     * dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])
     *
     * 第k+1次买入：
     * dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j][0]-prices[i])
     * 我们用两个循环来计算这个推导：
     *
     * 外层的循环是n，即遍历数组
     * 内层的循环是k，遍历k次交易
     * 最后求的利润最大值就保存在dp[n-1][k][0]中，我们直接返回即可。
     * 动态规划+空间优化
     * 我们对三维数组进行压缩，去掉最高维度的天数n，用二维数组dp[k][2]来代替。
     * 这里的k就是交易了多少次，2表示买卖状态。
     *
     *
     * 初始状态为 dp[0[0]
     * 第一次买dp[0][1]、第一次卖dp[1][0]
     * 第二次买dp[1][1]、第二次卖dp[2][0]
     * 第k次买dp[k-1][1]、第k次卖dp[k][0]
     * 因为初始化状态是dp[0][0]，所以后面每次买和卖的时候，数组第一个维度都需要+1。这里和三维数组推导是类似的。
     * 第k次买入的定义是dp[k-1][1]，第k次卖出的状态定义是dp[k][0]
     * 同样dp[k][1]这种状态也是不存在的。
     *
     * DP公式如下：
     *
     *
     * dp[j-1][1] = max(dp[j-1][1],dp[j-1][0]-prices[i])
     * dp[j][0] = max(dp[j][0],dp[j-1][1]+prices[i])
     * 我们用两个循环来计算这个推导：
     *
     * 外层的循环是n，即遍历数组
     * 内层的循环是k，遍历k次交易
     * 由于对dp数组进行了压缩，所以内层循环采用的是逆序遍历。
     * 这是因为状态压缩之后，由于少了一个维度，正序遍历会出现状态覆盖的情况，所以改成了逆序遍历。
     * 这种情况在很多dp压缩的时候都会出现，比如背包类型的dp，如果做了状态压缩，也是需要逆序遍历。
     * 关于倒序的问题参考了 这里
     *
     * 作者：wang_ni_ma
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/si-chong-jie-fa-tu-jie-188mai-mai-gu-piao-de-zui-j/
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit_2(int k, int[] prices) {
        if (prices==null||prices.length==0){
            return 0;
        }
        int n = prices.length;
        //当k非常大时转为无限次交易
        if (k>=n/2){
            int dp0=0,dp1=-prices[0];
            for (int i = 1; i < n; i++) {
                dp0=Math.max(dp0,dp1+prices[i]);
                dp1=Math.max(dp1,dp0-prices[i]);
            }
            return Math.max(dp0,dp1);
        }

        //定义二维数组，交易了多少次、当前的买卖状态
        int[][] dp = new int[k+1][2];
        //初始化
        for (int i = k; i >= 0; i--) {
            dp[i][0]=0;
            dp[i][1]=-prices[0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = k; j > 0; j--) {
                //第K次买入
                dp[j-1][1]=Math.max(dp[j-1][1],dp[j-1][0]-prices[i]);
                //第K次卖出
                dp[j][0]=Math.max(dp[j][0],dp[j-1][1]+prices[i]);
            }
        }
        return dp[k][0];
    }

    public int maxProfit_3(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        //当k非常大时转为无限次交易
        if (k >= n / 2) {
            int dp0 = 0, dp1 = -prices[0];
            for (int i = 1; i < n; i++) {
                dp0 = Math.max(dp0, dp1 + prices[i]);
                dp1 = Math.max(dp1, dp0 - prices[i]);
            }
            return Math.max(dp0, dp1);
        }
        // 状态转移方程里下标有 -1 的时候，为了防止数组下标越界，多开一行，因此第一维的长度是 len + 1
        // 第二维表示交易次数，从 0 开始，因此第二维的长度是 k + 1
        // 第三维表示是否持股，0：不持股，1：持股
        int[][][] dp = new int[n + 1][k + 1][2];

        // 初始化：把持股的部分都设置为一个较小的负值
        // 注意：如果使用默认值 0，状态转移的过程中会做出错误的决策
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j][1] = Integer.MIN_VALUE;
            }
        }

        // 注意：i 和 j 都有 1 个位置的偏移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1]);
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
            }
        }
        // 说明：第一维和第二维状态都具有前缀性质的，输出最后一个状态即可
        return dp[n][k][0];

//        作者：liweiwei1419
//        链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/dong-tai-gui-hua-by-liweiwei1419-4/
    }
}
